Cách mạng Dân tộc Indonesia xảy ra lúc Solihin học trung học và ông gia nhập Lực lượng vũ trang Indonesia; ông tham gia kỳ thi cuối kỳ trong quân phục chiến đấu. Ông đấu tranh chống lại Đảng Cộng sản Indonesia sau Vụ Madiun năm 1948.[3] Sau đó, ông tham gia các hoạt động chống lại cuộc nổi loạn Hồi giáo Darul ở Tây Java.[4] Lúc đầu, ông được phân công đến Quân khu Siliwangi (en) ở Tây Java, cùng nhiệm vụ ở Bangka khi là tư lệnh tiểu đoàn từ năm 1951 đến năm 1953. Ông học tại Đại học Chỉ huy và Tổng tham mưu Lục quân Indonesia từ năm 1953 đến năm 1954, giảng dạy tại trường từ năm 1954 đến năm 1956, và sau đó tham gia khóa học một năm tại Hoa Kỳ.[2]

Sau khi hoàn thành việc học, ông trở lại Quân khu Siliwangi và phục vụ đến năm 1964. Ông sau đó chuyển đến Quân khu Hasanuddin (en) ở Nam Sulawesi, tham gia các hoạt động chống lại nhánh Hồi giáo Darul của Abdul Kahar Muzakkar (en). Ông trở thành tư lệnh Quân khu Hasanuddin vào năm 1965. Theo một giai thoại được kể lại trong tiểu sử của người tiền nhiệm Mohammad Jusuf (en), Solihin đã ngủ trong một nghi lễ thì Jusuf bất ngờ chỉ định Solihin là người kế nhiệm, và sĩ quan phụ tá của Solihin phải đánh thức ông để báo cho biết về việc này.[2][5] Ông được bổ nhiệm giữ chức thống đốc bộ phận lục quân của Học viện Lực lượng Vũ trang Indonesia (AKABRI Bagian Darat) vào ngày 15 tháng 7 năm 1968.[6] Quân hàm cuối cùng của ông trong quân đội là trung tướng.[5]